\section{Optimizing social welfare: NP-completeness and approximation algorithms}
\label{sec:game.social}

\subsection{NP-completeness of computing the social optimum}
We show that computing the social optimum is NP-complete in $\GNS{d}$
games for all $d$.  The result for $d = \infty$ follows from Aspnes et
al.~\cite{AspnesCY2006}, even for the special case where all security
costs, infection costs, and initial infection probabilities are
uniform.  We now establish NP-completeness for all $d>0$.

\iffalse
\begin{lemma}
\label{lemma:game.socopt-npc}
Computing the social optimum for an instance of $\GNS{1}$ is
NP-complete, even when all nodes have the same costs.
\end{lemma}
\begin{proof}
This problem is clearly in NP. We reduce vertex cover in order to
prove the NP-hardness.  An instance of vertex cover consists of an
undirected graph $G$ and an integer $k$, and the goal is to determine
whether there is a set $S$ of at most $k$ vertices such that every
edge is incident on at least one of the vertices in $S$.  It is
well-known that the vertex cover problem is
NP-complete~\cite{garey+j:NP}.  We construct an instance $\mathcal{I}$
of $\GNS{1}$ on graph $G$ with $C=\frac{L}{n}+1$. For a pure strategy
vector $\vec{a}$ in which set $A$ of nodes is vaccinated, with
$|A|=a$, we have
\begin{eqnarray*}
\cost(\vec{a}) &=& Ca + (n-a)\frac{L}{n} + \frac{L}{n}|\{e=(u,v): a_u
= a_v = 0\}|\\ &=& L + (C-\frac{L}{n})a + \frac{L}{n}|\{e=(u,v): a_u =
a_v = 0\}|\\ &=& L+a + \frac{L}{n}|\{e=(u,v): a_u = a_v = 0\}|
\end{eqnarray*}
Therefore, if the set $A$ forms a vertex cover for $G$, for every edge
$e=(u,v)$, $u\in A$ or $v\in A$. This implies that if $G$ has a vertex
cover of size at most $k$, $\mathcal{I}$ has a social optimum of cost at most
$L+k$. Conversely, if $G$ has no vertex cover of size at most $k$, the
social optimum in $\mathcal{I}$ has cost strictly larger than $L+k$.
Therefore, the lemma follows.
\end{proof}
\fi

\begin{lemma}
\label{lemma:game.gensocopt-npc}
Computing the social optimum for an instance of $\GNS{d}$ is
NP-complete for all $d$.
\end{lemma}
\begin{proof}
We construct a reduction from vertex cover on regular graphs, which is
also NP-complete~\cite{feige03}. Consider an instance of vertex cover
specified by an $r$-regular graph $G=(V,E)$.  We construct an instance
$\mathcal{I}$ of the $\GNS{d}$ problem as follows.  Let
$H=(V',E')$ be a graph obtained by splitting each edge $e=(u,v)\in E$
by $d-1$ auxiliary nodes $v_{e,1},\ldots,v_{e,d-1}$, so that $V'=V\cup
\cup_{e\in E} \{v_{e,1},\ldots,v_{e,d-1}\}$, and $E'$ consists of the
edges $\cup_{e=(u,v)\in E}\{(u, v_{e,1}), (v, v_{e,d-1}),
(v_{e,1},v_{e,2}),\ldots, (v_{e,d-2}, v_{e,d-1})\}$. For all nodes
$v\in V$, let them have the same secure cost $C$ and infection cost $L$. And we set $C = \frac{L\left(r(d-1)+1\right)}{|V'|}+1$. For each $u\in
V'\setminus V$, we have $L_u = 1/|V'|^3$ and $C_u = (C+L)|V'|$\junk{$C_i =
\frac{L_idr}{|V'|}$}. This ensures all nodes in $V'\setminus V$
are insecure, and $\sum_{u\in V'\setminus V}
\cost_u(\vec{a})\leq\epsilon$ for small constant $\epsilon$, for any
strategy $\vec{a}$.

Let $B=\{v\in V: a_v=1\}$ for a pure strategy $\vec{a}$, and let
$b=|B|$. It is easy to verify that
%Following the same calculation as in the proof of Lemma
%\ref{lemma:game.socopt-npc}, we have 
$\cost(\vec{a}) =
\frac{L|V|\left(r(d-1)+1\right)}{|V'|} + b + \epsilon+ \frac{2L}{|V'|}|\{e=(u,v): u,
v\in V, a_u = a_v = 0\}|$. Therefore, when we set $L > |V|\cdot |V'|$, $B$ is a vertex cover in $G$ of
size $k$, if and only if the social optimum in $\mathcal{I}$ is at
most $\frac{L|V|\left(r(d-1)+1\right)}{|V'|} + k + \epsilon$.
\end{proof}

For $d = 1$, we also show that while a pure NE always exists, finding
the least cost one is NP-complete.

\begin{lemma}
\label{lemma:game.ne-npc}
Finding the least cost pure NE in a given instance of $\GNS{1}$ is
NP-complete.
\end{lemma}
\begin{proof}
Our proof is a reduction from Vertex Cover.  Let $G$ be an instance of
vertex cover.  We construct an instance $\mathcal{I}$ of the game in
the following manner.  We set the contact graph
to be $H=(V', E')$ with $V'=V\cup\cup_{i\in V} A(i)$, where the set
$A(i)=\{v_{i,1},\ldots,v_{i,t}\}$, for $t\geq \Delta(G)$, where
$\Delta(G)$ is the maximum degree of $G$.  The set $E'$ consists of
$E$ along with the edges $(i,j)$, for all $i\in V$ and $j\in A(i)$.
The security and infection costs for all nodes in $V$ are
identical, $C$ and $L$, respectively.  Set $C = \frac{(t+1)L}{|V'|}+1$.  For nodes
in $V'\setminus V$, these corresponding costs are $C'=L'(1+\epsilon)/|V'|$ and
$L'=1/M$, respectively, where $M\geq |V'|^2t$.  We assume that the
initial infection probability distribution is uniform.  Therefore, the
contribution, $\cost_v(\vec{a})$ of a node $v\in V'\setminus V$ to the
total cost $\cost(\vec{a})$ for any strategy vector $\vec{a}$ is at
most $\max\{C',2L'/|V'|\}$, and the total contribution of all such nodes
is at most $1$.  We show that the least cost NE has cost very close to
the social optimum.

Let $A$ be a vertex cover for $G$, with $|A|=a$. Consider the
following strategy vector $\vec{a}$: for each $i\in A$, we have
$a_i=1$ and $a_{v_{i,j}}=0$ for all $j$, and for $i\not\in A$, we have
$a_i=0$ and $a_{v_{i,j}}=1$ for all $j$.  Following Lemma
\ref{lemma:game.nechar}, this vector is a NE because: (i) for each node
$i\in A$, there are at least $t$ insecure neighbors (namely, the nodes
$v_{i,j}$), (ii) for each $i\not\in A$, the number of insecure
neighbors is at most $\Delta(G)\leq C|V'|/L$, where $\Delta(G)$ is the
maximum degree of $G$, (iii) if $i\in A$, each node $v_{i,j}$ has no
insecure neighbor, and since $C'|V'|/L'=1+\epsilon$, such a node won't change its strategy, and
(iv) if $i\not\in A$, each node $v_{i,j}$ has an insecure neighbor and it will stay being secure.  As in the proof of Lemma
\ref{lemma:game.gensocopt-npc}, $\cost(\vec{a})\leq L+|A|+1$. Therefore, if $G$
has a vertex cover of size $k$, the reduced game instance has a pure NE of
cost at most $L+k+1$.

For the converse, let $\vec{a}$ be the strategy vector of a NE, and $A=\{i: a_i=1\}\cap V$. As in the proof of Lemma
\ref{lemma:game.gensocopt-npc}, $\cost(\vec{a}) = 
L+|A|+\frac{2L}{|V'|}|\{(u,v): a_u=a_v=0,\ u,v\in V\}|$, which implies
if $A$ is not a vertex cover for $G$,
$\cost(\vec{a})>L+|A|$. Therefore, the lemma follows.
\end{proof}

\subsection{Approximating the social optimum}

We describe a general framework to derive approximation algorithms for
$\GNS{d}$ games for all $d$.  For fixed $d$, we achieve an
approximation ratio of $2d$.  For $d = \infty$, we obtain an
approximation ratio of $O(\log n)$.  Our framework involves the
following three steps.
\begin{enumerate}
\item
Formulate a linear programming relaxation.
\item
Let $\textbf{x}$ be the optimum LP solution.
Partially round and filter the variables. Let $\textbf{x}'$ be
the resulting solution.
\item
Round the $\textbf{x}'$ solution appropriately - for constant $d$, this
involves solving a suitable covering problem, while for $d=\infty$ this
reduces to a vertex separator problem.
\end{enumerate}

%In \cite{AspnesCY2006}, Aspnes et al gave an $O(\log^2 n)$-approximation algorithm for the social optimal. Here we are going to improve the approximation ratio to $O(\log n)$.

%\subsubsection{$\left(O(\log n),O(1)\right)$-approximation}
\subsubsection{An LP Formulation}
\label{sec:game.socopt-lp}

Let $P^d_{ij}$ denote the set of all simple paths from $i$ to $j$ of
length at most $d$.  Let $x_v$ be the indicator variable for node $v$
that is 1 if $v$ is secured.  Let $y_{ij}$ be the indicator variable
for nodes $i$ and $j$ that is 1 if there is no path $P\in P^d_{ij}$
consisting entirely of insecure nodes. By abuse of notation, for
$i=j$, we assume $y_{ii}=1$ if node $i$ has been secured, i.e.,
$x_i=1$. We start with the following integer programming formulation
${\cal P}$ of the social optimum.

\junk{%First we write down the integral LP for Aspnes' problem. $x_v =
      %1$ if vertex $v$ takes vaccine; $y_{ij} = 1$ if $i$ and $j$ are
      %disconnected after removing vaccinated nodes (a node is always
      %connecting to itself); $C$ is the cost of vaccination; $L$ is
      %the lost if one gets infected; $P_{ij}$ is the set of all paths
      %from $i$ to $j$.
}

\begin{eqnarray}
\min & \sum_{v} C_v\cdot x_v + \sum_{j\in V} L_j \sum_{i \in V} w_i(1-y_{ij})  \nonumber \\
\mbox{s.t.} & \sum_{v\in p} x_v\ge y_{ij} \,\, p\in P^d_{ij}   \label{constraint}\\
& x_v \in \{0,1\}  \,\,\forall v\in V \nonumber\\
& y_{ij} \in \{0,1\}  \,\, \forall i,j\in V \nonumber
\end{eqnarray}

The objective function can be interpreted in the following manner: the
first part corresponds to the cost of securing nodes, and the second
part corresponds to the infection cost, which, for node $j$ is $L_j$
times the sum of the probabilities of all nodes that have a path to
$j$ of length at most $d$ consisting entirely of insecure nodes.  The
first constraint says that in order to separate a pair of nodes $i$
and $j$, we need to secure at least one node in every path $P\in
P^d_{ij}$ between these two.  For $i=j$, we define the only path $P$
in $P^d_{ij}$ to consist of the node $i$.

%Social optimal is defined to be the sum of each individual's cost, which is $C\cdot\{\#$\textit{number of vaccinated nodes}$\}+\frac{L}{n}\sum_{i=1}^l k_i^2$ where $k_1,k_2,\dots,k_l$ are the sizes of the connected components in the residual graph. The objective of the LP is the same as social cost. And the first constraint says in order to separate a pair of nodes, we need to remove at least one node in every path between these two.
We relax the IP to a linear program (LP) by changing the last two constraints to 
$0\le x_v\le 1$ and $0\le y_{ij}\le 1$. 

\subsubsection{Solving the LP and partial rounding and filtering}
We now perform the following steps.

\noindent
(1) Solve the LP: for any fixed $d$, the number of paths of length at
most $d$, $|P^d_{ij}|$ is at most $n^{O(1)}$, and therefore, the above
program can be solved in polynomial time.  When $d$ is not a constant,
the program cannot be written down efficiently but we can solve it in
polynomial time using the ellipsoid method. This requires the
construction of a polynomial time separation oracle, which, given a
candidate solution $(\vec{x}, \vec{y})$, can decide if it is feasible,
or finds a constraint that is infeasible. Such a separation oracle can
be designed as follows: define the cost of a path to be the sum of the
weights $x_v$ of the nodes on the path. For each pair $i,j$, compute
the shortest path from $i$ to $j$ in the graph restricted to the
$d$-hop neighborhood of node $i$.  If this distance exceeds $y_{ij}$,
the constraints for all the paths $p\in P^d_{ij}$ are satisfied. Else,
the constraint corresponding to the shortest such path is violated.

Ellipsoid-based methods are, however, expensive to implement in
practice.  For the case $d = \infty$, we address this drawback by
solving an equivalent polynomial-sized LP in which we introduce a
``distance variable'' for each pair of nodes and replace the
exponentially-many path constraints given in (\ref{constraint}) with
polynomially-many triangle inequality constraints, and linear number
of lower bounds on the distances.  It is this more compact LP that we
solve in our experiments.

\noindent
(2) Construct a new vector $\vec{y}'$ in the following manner: for
each $i,j$, $y'_{ij}=0$ if $y_{ij}\leq 1/2$ and $y'_{ij}=1$ if
$y_{ij}>1/2$.  Next, let $x'_v = \min\{2x_v,1\}$, for all $v\in V$.
%Solve the LP, and get fractional values for $x_v$'s and $y_{ij}$'s. If $y_{ij} < 1/2$, it contributes a lot to the LP. We make it to 0. If $y_{ij} > 1/2$, it contributes little to the LP. We make it to 1. Now we double the values of $x_v$'s. If the value is more than 1, we make it equal to 1. Call the new values $x'_v$'s and $y'_{ij}$'s. This solution is still a feasible solution of the LP, and the cost of the objective function is within twice the optimal. This fractional solution can be seen as a solution that separate those pairs with $y'_{ij}=1$. 

\subsubsection{Final rounding}
We now round the vector $\vec{x}'$ to an integral solution. For $d=1$,
it is easy to see that $\vec{x}'$ is already integral, since each
constraint only has two variables.  We now consider general $d$.
Consider a pair of nodes $i$ and $j$ such that $y'_{ij} = 1$.  By
constraint~(\ref{constraint}), along every path $p$ of length at most
$d$ between $i$ and $j$, the sum, over $v \in p$, of $x'_v$ is at
least $1$.  It follows that along every such path $p$, there exists at
least one vertex $v \in p$ with $x'_v \ge 1/d$.  Consider now the
following filtering procedure: if $x'_v \le 1/d$, we set $x''_v = 0$;
otherwise, we set $x''_v = 1$.  It is clear that all the constraints
of the LP are satisfied, and the cost of $\vec{x''}$ is at most $d$
times the cost of $\vec{x'}$, yielding a final $2d$ approximation.

We finally consider the $d = \infty$ case.  In this case, we are left
with a minimum weighted vertex multi-cut problem, where we would like
to determine the minimum weight of vertices that can separate all the
pairs $(i,j)$ for which $y'_{ij} = 1$.  The elegant LP rounding
algorithm of~\cite{garg+vy:multicut} yields an integral solution for
the vertex multi-cut problem, whose cost is $O(\log n)$ times the cost
of fractional solution.  We can thus find a set $X$ of vertices to
secure such that all pairs of vertices for which $y'_{ij} = 1$ are
separated and $\sum_{v \in X} C_v$ is at most $O((\log n) \sum_v C_v
x'_v)$.  

Putting the above analyses together, we have the following.

\begin{theorem}
For any fixed $d$, the social optimum for an instance of $\GNS{d}$ can
be approximated to within a factor of $2d$ in polynomial time.  For
$d=\infty$, we obtain an $O(\log n)$-approximation to the social
optimum, where $n$ is the number of nodes in the contact graph.
\end{theorem}

%We call the vertex multicut procedure to find the integral solution, which is an $O(\log n)$-approximation on $\sum_{v} C\cdot x_v$ part. And we have $O(1)$-approximation on $\sum_{i,j\in V} \frac{L}{n}\cdot (1-y_{ij})$ part. So in sum, this is an $O(\log n)$ of the social optimal.

